1. Field of the Invention
This invention relates to the field of computer and programming systems, and in particular to the programming of systems that employ circular lists or iteratively process multiple-word operands.
2. Description of Related Art
Circular lists are often used to implement First-In, First-Out (FIFO) buffers. The FIFO model represents a list of items wherein new items are added to the top of the list, and old items are removed from the bottom of the list. In effect, the FIFO is structured as a list of L data items; when a data item is added to the list, it is given the next available address of L+1; when a data item is removed from the list, the address of each data item remaining in the list is decremented by one. The moving of each remaining data item down in the list each time a data item is removed from the list, however, is inefficient. Instead, the defined xe2x80x9cbottomxe2x80x9d of the list is moved up by one each time a data item is removed. The logical address of each data-item in the list is defined by its distance from this defined bottom of the list, rather than by its physical location in the continually growing list. Even though the xe2x80x9cremovedxe2x80x9d data items may remain in the physical locations below the xe2x80x9cbottomxe2x80x9d of the list, they are no longer within the logical address space of the list, and are no longer considered to be a part of the list of L items. As would be evident to one of ordinary skill in the art, the continued advancement of the physical location used for each added data item, without a corresponding physical relocation of each data item to lower physical locations as data items are removed, will eventually exhaust the physical resources used to contain these data items.
A circular list is embodied as N contiguous physical memory locations, and a corresponding controlling mechanism that adds new data items to the list, starting at the beginning of the physical memory locations, and continuing to each next available physical location until the end of the contiguous locations is reached. When the next data item arrives after reaching the end of the contiguous locations, this next data item is placed at the beginning of the contiguous locations, replacing the prior data item that was stored at the beginning of the contiguous locations. Each next data item is placed into each next physical location, replacing the data items previously stored at each next physical location, until the end of the contiguous locations is again exceeded, at which point the next data item is placed at the beginning of the contiguous locations. This process continues ad infinitum without consuming more than the N contiguous physical memory locations at any time. Note, however, that the prior data items that are being replaced by the next data items must have been data items that were conceptually xe2x80x9cremovedxe2x80x9d from the list. That is, at no time can the logical length of the list, L, exceed the physical length of the contiguous locations N. In a typical embodiment, the controlling mechanism maintains a pointer to the logical xe2x80x9cbottomxe2x80x9d of the list, and updates it accordingly as each data item is removed from the list, and also maintains a pointer to the logical xe2x80x9ctopxe2x80x9d of the list, and updates it accordingly as each data item is added to the list. The controlling mechanism also inhibits the addition of a new data item when the xe2x80x9ctopxe2x80x9d of the list becomes coincident with the xe2x80x9cbottomxe2x80x9d of the list, and waits for the xe2x80x9cbottomxe2x80x9d of the list to be advanced (by a removal of the oldest item in the list) before placing the new data item into the list.
Typically, multiple programming instructions are required to control the incrementing and decrementing of a pointer that is associated with a circular list. The instructions must test whether the pointer has gone beyond the upper or lower bounds of the physically contiguous memory locations, and adjust the pointer accordingly to provide the circular addressing effect.
It is an object of this invention to provide a device that facilitates the use of circular lists. It is a further object of this invention to ease the task of programming a device to facilitate the use of circular lists. It is a further object of this invention to ease the task of programming a device to facilitate the use of multiple-word data items by modeling the multiple-word data items as circular addressing process.
These objects and others are achieved by providing a device and corresponding programming instructions that facilitate a circular addressing process. The device is configured to provide an address output that is constrained to lie within specified bounds. When a xe2x80x9ccircular incrementxe2x80x9d or xe2x80x9ccircular decrementxe2x80x9d instruction is executed that would cause the address to exceed a bound, the address is reset to the other bound. In a preferred embodiment, the programming instruction also sets condition flags that indicate when the address is at each bound. By providing these xe2x80x9cboundsxe2x80x9d flags in conjunction with the circular addressing operation, multiple-word data items can be processed efficiently. A base-address of N contiguous words in a memory is loaded into the circular register, and a circular addressing instruction is used to access each word of the N contiguous words in sequence; a bounds flag is set when the last word of the multi-word data item is accessed. This bounds flag may thus be used to signal the end of processing of N words of a multi-word data item, and can be used to trigger a load of a next multi-word data item, or to trigger a next operation on the current data-item, and so on. Other condition flags are also provided to facilitate the processing of multi-word data-items.